
\documentclass[11pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\F}{{\mathbb{F}}}
\newcommand{\eps}{\epsilon}
%\usepackage{psfig}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{fullpage, color}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

%{lecture number}{lecture documentate}{Elena Grigorescu}{Your name}
\lecture{2}{Aug 23, 2012}{Elena Grigorescu}{Jacques Pienaar}

\section{Overview}
\noindent In this lecture:
\begin{itemize}
        \item Basic facts about random variables and expectations;
        \item Markov's inequality;
        \item Chebyshev's inequality;
        \item Chernoff/Hoeffding's inequality; 
        \item Applications.
\end{itemize}

\section{Review of probability theory needed}
Let $D$ be a finite domain, then we call a function $p:D\to[0,1]$ a probability distribution if $\sum_{x\in D}p(x)=1$. Examples of common probability distributions are
\begin{itemize}
        \item Uniform distribution $u(x)=1/|D|$;
        \item Bernoulli distribution (corresponding to flipping a biased coin which gives heads with probability $q$ and tails with probability $1-q$)
        \[
                p(x) = \begin{cases}
                                        q &\text{if $x=1$}\\
                                        1-q &\text{if $x=0$}
                                \end{cases}
        \]
        \item Binomial distribution (corresponding to flipping a biased coin $n$ times)
        \[
                \Pr[\text{get $k$ heads in $n$ flips}] = \binom{n}{k}q^k(1-q)^{n-k}.
        \]
\end{itemize}

\begin{definition}
        A \emph{random variable} is a function $V:D\to S\subset \R$.
\end{definition}
\begin{definition}[Expectation]
        For a random variable $V$ defined over domain $D$ and distributed according to a probability distribution $p$, we define the expectation of $V$ as
        \[
                E[V] \equiv \sum_{x\in D}p(x)V(x).
        \]
\end{definition}
\begin{definition}[Indicator random variable]
        Given an event $A$, we define the indicator random variable of $A$ as
        \[
                I_A:=\begin{cases}
                        1 &\text{if $A$ is true}\\
                        0 &\text{else}.
                \end{cases}
        \]
\end{definition}
\begin{proposition}
  %      The expected value of the indicator function of an event $E$ is equal to the probability that $E$ will occur.
If $A$ is an event then $E[I_A]=\Pr[A]$,
\end{proposition}
\begin{proof}
        $E[I_A]=1\cdot \Pr[{\text{$A$ is true}}] + 0\cdot \Pr[{\text{$A$ is false}}]$. 
\end{proof}
\begin{definition}[Pairwise independence]
        We call two random variables, $A$ and $B$, over $D$ pairwise independent if for all $a,b\in D$, $\Pr[{A=a\land B=b}]=\Pr[{A=a}]\cdot \Pr[{B=b}]$.
\end{definition}
\begin{fact}(Linearity of expectation)
        For any two random variables $A$, $B$ (not necessarily independent) over $D$ we have $E[A+B]=E[A]+E[B]$.  
\end{fact}
Examples:
\begin{itemize}
        \item $E[\text{sum of 3 dice}] = 3\cdot 7/2$
        \item Expected value of a binomial distribution. Let us flip $n$ biased coins (with each coin having $q$ probability of head, $1-q$ the probability of landing tails). Denote with $X_i$ the indicator variable that the $i^\text{th}$ coin landed heads. Then $X=\sum_{i=1\ldots n}{X_i}$ is the random variable for the number of heads, and its expectation is 
        \begin{align*}
                E[X] &= E\left[\sum_{1\ldots n} X_i\right]
                =\sum_{i=1\ldots n} E[X_i]\\
                &=\sum_{i=1\ldots n} q = nq.
        \end{align*}
\end{itemize}
\begin{proposition}
        If $A$ and $B$ are pairwise independent then $E[A B]=E[A]E[B]$.
\end{proposition}
\begin{definition}[Conditional probability]
        For two random variables $A$ and $B$ over the domain $D$ the conditional probability of event $A$ occurring given that $B$ occurs, denoted $\Pr[{A \mid B}]$, is defined as follows
        \[
                \Pr[{A\mid B}] = \frac{\Pr[{A\land B}]}{\Pr[{B}]}.
        \]
\end{definition}
\begin{definition}[Conditional expectation]
        For a random variable $X$ over a domain $D$,
        \[
                E[X\mid A]=\sum_{x\in D}\Pr[{X=x\mid A}]\cdot x.
        \]
\end{definition}
For example, the expected value of a roll of a die, given the event $A$ that we rolled something less than 3 is
\[
        E[X\mid A]
                = \sum_{x=1,2,3} \Pr[{X=x\mid A}]\cdot x
                = 1\cdot 1/3+2\cdot 1/3+3\cdot1/3+0=2.
\]
\begin{proposition}[Union bound] Given events $E_1$ and $E_2$,the probability that at least one happens is bounded by 
        $\Pr[{E_1\cup E_2}]\leq  \Pr[{E_1}]+\Pr[{E_2}]$.
\end{proposition}

For example, if we roll $3$ dice, then $\Pr[\text{at least one } =6]\leq 3\cdot 1/6$.

\begin{theorem}[Markov's inequality]
        Let $X$ be a non-zero, random variable, and $a>0$ then
        \[
                \Pr[{|X|\geq a}]\leq \frac{E[|X|]}{a}.
        \]
        Or equivalently $\Pr[|X| \geq a E[|X|]]\leq 1/a$.
\end{theorem}

As an example, for the toss of $n$ fair coins let $X_i$ denote the event that the $i^\text{th}$ coin lands heads. Then
$E[\sum X_i]=n/2$ so the probability that more than
$2/3$'s of the coins come up heads is
\[
        \Pr[{\text{$2n/3$ come up heads}}] \leq \frac{n/2}{2n/3}=\frac{3}{4}.
\] 

\begin{theorem}[Chebyshev's inequality]
        \[
                \Pr[{|X-E[X]|\geq a}]\leq \frac{\Var[X]}{a^2},
        \]
        where $\Var[X]:=E[(X-E[X])^2]$.
\end{theorem}
\begin{proof}Let random variable $Y=|X-E[X]|$. Using Markov's inequality we have that 
        \[
                \Pr[{Y\geq a}] = \Pr[{Y^2\geq a^2}]
                \leq \frac{E[Y^2]}{a^2}=\frac{\Var[X]}{a^2}.
        \]
\end{proof}
\begin{theorem}[Chernoff/Hoeffding inequality]
        Let $X_1$, $\ldots$, $X_n$ be independent random variables in the interval $[0,1]$ and let $X=\sum X_i$. Then
        \[
                \Pr[{|X-E[X]|\geq t}]\leq 2\exp\left(-2t^2/n\right).
        \]
        Equivalently 
        \[
                \Pr[{|X-E[X]|\geq \eps\cdot E[X]}]\leq 2\exp\left(-2\eps^2E[X]^2/n\right),
        \]
        and 
        \[
        \Pr[{|X-E[X]|\geq \eps n}]\leq 2\exp\left(-2\eps^2n\right).
        \]
\end{theorem}

\section{Applications}
In this section we shall discuss two applications of the Chernoff bound.


\subsection{Approximating the fraction of 1's in a binary string}
 Suppose we want to estimate the fraction of 1's in a given string $S\subset \{0,1\}^n$. That is, we wish to find a fast randomized algorithm that, given $\eps$ and string $S$ outputs a value $V$ such that $|V-\text{fraction of 1's}|<\eps$ with probability $2/3$.

\begin{description}
        \item[Algorithm] Pick $k=1/\eps^2$ uniformly random indices in the string $S$ and output the fraction of 1's in the sample.
        \item[Analysis] Let $X_1$, $\ldots$, $X_k$ be random variables indicating if a 1 was found in the string position for the $i^\text{th}$ index selected ($1\leq i\leq k$). It follows that $E[X_i]$ is equal to the fraction of 1's in $S$. Let $X$ be the random variable for the number of 1's in the sample, so $X=\sum X_i$ and the indicator variable for the value output by the algorithm (i.e. for the fraction of $1$'s in the sample) is $\frac{X}{k}$. Then by Chernoff's bound
        \[
                \Pr\left[{\left|\frac{X}{k}-\frac{E[X]}{k}\right|>\eps}\right]
                \leq 2e^{-2\eps^2k}= 2e^{-2}<1/3
        \]
        as $\eps^2k=1$.
        
        Therefore 
        \[
        \Pr\left[\left|\frac{X}{k}-E[X_i]\right|>\eps\right]<1/3,
        \]
        meaning that we output a good estimate (i.e. within $\eps$ from the true fraction of $1$'s in the string) with probability $>2/3$.
\end{description}

\subsection{Improving a random algorithm's correctness}
Suppose we are given a randomized algorithm $A$ which on each input $x$ from some domain $D$ outputs a $0$ or $1$ answer and it is correct with probability $p=2/3$. (In other words there is some function $f:D\rightarrow \{0,1\}$ such that, for any $x\in D$ we have that $\Pr[A(x)=f(x)]\geq 2/3$, where the probability is computed over the randomness of the algorithm $A$.) Let algorithm $B$ run $A$ for $t$ times and output the majority answer. We next show that algorithm $B$ is correct (on each input) with probability greater than $1-2^{-ct}$ for some
constant $c$ (that is, $\forall x\in D$, $Pr[B(x)=f(x)]\geq 1-2^{-ct}.$)

        {\bf Analysis} Fix some input $x$. Let $X_1$, $\ldots$, $X_t$ be indicator variables such that $X_i=1$ if $A$ outputs the correct answer in the $i^\text{th}$ step. Therefore, $E[X_i]=p=2/3$. Set $X=\sum X_i$, that is $X$ is the random variable counting the number of correct answers, and notice that $E[X]=2t/3$.
        \begin{align*}
                \Pr[{\text{$B$ outputs incorrect answer}}]
                &=\Pr[{\text{$A$ outputs incorrect answer more than $t/2$ times}}]\\
                &=\Pr[{X<t/2}]
                \leq \Pr[{X-2t/3<t/2-2t/3}]\\
                &= \Pr[{X-2t/3<-t/6}]
                \leq \Pr[{|X-2t/3|>t/6}]\\
                &\leq 2e^{-2t^2(1/6)^2/t}=2^{-ct}.
        \end{align*}

\end{document}
